#include "StdAfx.h"
#include "MinHeap.h"
#include "RelatedFun.h"
#include <stdlib.h>

namespace WTB{

	CAbstractHeap::CAbstractHeap(void)
		:m_uCurrentHeapSize(0),
		m_uMaxHeapSize(0),
		m_arrNodePoint(NULL)
	{
	}

	CAbstractHeap::~CAbstractHeap(void)
	{
		if (m_arrNodePoint)
		{
			free(m_arrNodePoint);
			m_arrNodePoint = NULL;
		}
	}

	int CAbstractHeap::InsertHeapNode(CAbstractHeapNode* _pNode){
		if (_pNode->GetHeapIndex() != CAbstractHeapNode::MAX_INDEX_PLUS_1)
		{
			return -1;
		}
		if (ReserveHeap(m_uCurrentHeapSize + 1) == -1)
		{
			return -1;
		}
		unsigned uHoleIndex = m_uCurrentHeapSize++;
		ShiftUpHeap(uHoleIndex,_pNode);
		return 0;
	}
	void CAbstractHeap::DropHeapNode(CAbstractHeapNode* _pNode){
		unsigned uIndex = _pNode->GetHeapIndex();
		if (uIndex == CAbstractHeapNode::MAX_INDEX_PLUS_1)
		{
			return;
		}
		DropHeapNode(uIndex);
	}
	CAbstractHeapNode* CAbstractHeap::PopHeapNode(){
		CAbstractHeapNode* pNode = NULL;
		if (m_uCurrentHeapSize > 0)
		{
			pNode = m_arrNodePoint[HEAP_ROOT_INDEX];
			DropHeapNode(HEAP_ROOT_INDEX);
		}
		return pNode;
	}
	int CAbstractHeap::ReserveHeap(unsigned _uSize){
		if (m_uMaxHeapSize < _uSize)
		{
			if (m_uMaxHeapSize > MAX_HEAP_SIZE / 2)
			{
				return -1;
			}
			unsigned uNewMaxSize = m_uMaxHeapSize ? m_uMaxHeapSize * 2 : 1024;
			if (uNewMaxSize < _uSize)
			{
				uNewMaxSize = _uSize;
			}
			CAbstractHeapNode** arrNodePoint;
			if (!(arrNodePoint = (CAbstractHeapNode**)realloc(m_arrNodePoint,uNewMaxSize*sizeof(*arrNodePoint))))
			{
				return -1;
			}
			m_arrNodePoint = arrNodePoint;
			m_uMaxHeapSize = uNewMaxSize;
		}
		return 0;
	}

}